package com.bee.剑指offer;

import java.util.HashMap;
import java.util.Map;

public class 判断链表中是否有环 {

    /**
     * 使用map实现
     */
    public boolean hasCycle(ListNode head) {
        Map<ListNode, String> map = new HashMap<>();
        while (head != null) {
            if (map.containsKey(head)) {
                return true;
            }
            map.put(head, "1");
            head = head.next;
        }
        return false;
    }

    /**
     * 快慢指针法
     */
    public boolean hasCycle2(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }


    public static void main(String[] args) {

    }
}
